package LeetCode.exercise;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class LC239 {
    public static void main(String[] args) {
        LC239 main = new LC239();
        int[] nums = new int[]{9,10,9,-7,-4,-8,2,-6};

        int[] ints = main.maxSlidingWindow(nums, 5);
        System.out.println(Arrays.toString(ints));
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> heap =
                new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int n = nums.length, cur = 0;
        int[] res = new int[n-k+1];
        for(int i = 0, tmp = k; tmp > 0; tmp--, i++){
            heap.offer(new int[]{nums[i], i});
        }
        res[cur++] = heap.peek()[0];
        for (int i = k; i < n; i++) {
            heap.offer(new int[]{nums[i], i});
            while(heap.peek()[1] <= i-k){
                heap.poll();
            }
            res[cur++] = heap.peek()[0];
        }

        return res;
    }
//    public int[] maxSlidingWindow(int[] nums, int k) {  // 超时
//        PriorityQueue<Pair<Integer, Integer>> heap =
//                new PriorityQueue<>((a, b) -> b.getValue().compareTo(a.getValue()));
//        int n = nums.length, cur = 0;
//        int[] res = new int[n-k+1];
//        for(int i = 0, tmp = k-1; tmp > 0; tmp--, i++){
//            heap.offer(new Pair<>(i, nums[i]));
//        }
//
//        for(int i = k-1, j = 0; i < n; i++, j++){
//            heap.offer(new Pair<>(i, nums[i]));
//            res[cur++] = heap.peek().getValue();
//            heap.remove(new Pair<>(j, nums[j]));
//        }
//        return res;
}
